DSC 40B Practice Problems

State (but do not solve) the recurrence describing the run time of the following code, assuming that the input, arr, is a list of size $n$ .


def foo(arr, stop=None):
    if stop is None:
        stop = len(arr) - 1

    if stop < 0:
        return 1

    last = arr[stop]
    return last * foo(arr, stop - 1)

Solution

$T (n) = T (n - 1) + Θ (1)$

What is the solution of the below recurrence? State your answer using asymptotic notation as a function of $n$ .

T (n) = {\begin{cases} 5 T (n / 5) + Θ (n), & n > 1 \\ 1, & n = 1 \end{cases}

Solution

$Θ (n \log n)$

State (but do not solve) the recurrence describing the runtime of the following function.


def foo(n):
    if n < 10:
        print("Hello world.")
        return

    for i in range(n):
        print(i)

    for i in range(6):
        foo(n//3)

Solution

$T (n) = 6 T (n / 3) + Θ (n)$ .

Solve the below recurrence, stating the solution in asymptotic notation. Show your work.

T (n) = {\begin{cases} 2 T (n / 4) + Θ (n) & n > 1 \\ c & n = 1 \end{cases}

Solution

$Θ (n)$ .

We'll unroll several times:

\begin{aligned} T (n) & = 2 T (n / 4) + n \\ = 4 T (n / 16) + \frac{n}{2} + n \\ = 8 T (n / 64) + \frac{n}{4} + \frac{n}{2} + n \end{aligned}

The pattern seems to be that on the $k$ th unroll:

T (n) = 2^{k} T (\frac{n}{4^{k}}) + n (1 + \frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^{k - 1}})

The base case is reached when $k = \log_{4} n$ . Plugging this back in, we find:

T (n) = 2^{\log_{4} n} T (1) + n (1 + \frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^{\log_{4} n - 1}})

If you reached this point, you got most of the credit. If you're unsure of what to do with $2^{\log_{4} n}$ , there are a couple of ways foward.

The first (and easiest) way is to realize that $2^{\log_{4} n}$ is smaller than $2^{\log_{2} n} = n$ , so $2^{\log_{4} n} = O (n)$ . Similarly, we've seen the summation of $1 + 1 / 2 + 1 / 4 + \dots$ several times -- this is a geometric sum, and converges to 2 when there are infinitely many terms. There are a finite number of terms here, so the sum is $< 2$ . Altogether, we have:

T (n) = O (n) T (1) + n Θ (1) = Θ (n)

The second approach is to remember log properties to simplify $2^{\log_{4} n}$ to $\sqrt{n}$ . This can be seen by using the ``change of base'' formula:

\log_{b} x = \frac{\log_{a} x}{\log_{a} b} .

In this case:

\log_{4} n = \frac{\log_{2} n}{\log_{2} 4} = \frac{\log_{2} n}{2}

And therefore $2^{\log_{4} n} = 2^{(\log_{2} n) / 2} = {(2^{\log_{2} n})}^{1 / 2} = n^{1 / 2} = \sqrt{n}$ . This shows that the first term in the recurrence is $Θ (\sqrt{n})$ . The second term is still $Θ (n)$ , so the solution is $Θ (n)$ .

State (but do not solve) the recurrence describing the runtime of the following function.


def foo(n):
    if n < 1:
        return 0

    for i in range(n**2):
        print("here")

    foo(n/2)

Solution

$T (n) = {\begin{cases} Θ (1), & n = 1 \\ T (n / 2) + Θ (n^{2}), & n > 1 \end{cases}$

Consider the modification of mergesort shown below, where one of the recursive calls has been replaced by an in-place version of selection_sort. Recall that selection_sort takes $Θ (n^{2})$ time.


def kinda_mergesort(arr):
    """Sort array in-place."""
    if len(arr) > 1:
        middle = math.floor(len(arr) / 2)
        left = arr[:middle]
        right = arr[middle:]
        mergesort(left)
        selection_sort(right)
        merge(left, right, arr)

What is the time complexity of kinda_mergesort?

Solution

$Θ (n^{2})$

Solve the below recurrence, stating the solution in asymptotic notation. Show your work.

T (n) = {\begin{cases} T (n / 2) + Θ (n) & n > 1 \\ Θ (1) & n = 1 \end{cases}

Solution

$Θ (n)$ .

Unrolling several times, we find:

T (n) = T (n / 2) + n = T (n / 4) + \frac{n}{2} + n = T (n / 8) + \frac{n}{4} + \frac{n}{2} + n

On the $k$ th unroll, we'll get:

T (n) = T (n / 2^{k}) + [n + \frac{n}{2} + \frac{n}{4} + \dots + \frac{n}{2^{k - 1}}]

It will take $\log_{2} n$ unrolls to each the base case. Substituting this for $k$ , we get:

\begin{aligned} T (n) & = T (n / 2^{\log_{2} n}) + [n + \frac{n}{2} + \frac{n}{4} + \dots + \frac{n}{2^{(\log_{2} n) - 1}}] \\ = T (1) + n [1 + \frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^{(\log_{2} n) - 1}}] & = T (1) + c n \\ = Θ (1) + c n \\ = Θ (n) \end{aligned}

Solve the recurrence below, stating the solution in asymptotic notation. Show your work.

T (n) = {\begin{cases} 2 T (n / 4) + Θ (n), & n > 1 \\ 1, & n = 1 \end{cases}

Solution

$Θ (n)$

State (but do not solve) the recurrence describing the run time of the following code, assuming that the input, arr, is a list of size $n$ .


def foo(arr, stop=None):
    if stop is None:
        stop = len(arr) - 1

    if stop < 0:
        return 1

    last = arr[stop]
    return last * foo(arr, stop - 1)

Solution

$T (n) = T (n - 1) + Θ (1)$

Problems tagged with "recurrence relations"

Problem #011

Problem #012

Problem #028

Problem #044

Problem #056

Problem #068

Problem #071

Problem #082

Problem #085